/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.dubbo.rpc.cluster.loadbalance;

import org.apache.dubbo.common.URL;
import org.apache.dubbo.common.utils.StringUtils;
import org.apache.dubbo.rpc.Invocation;
import org.apache.dubbo.rpc.Invoker;
import org.apache.dubbo.rpc.cluster.ClusterInvoker;
import org.apache.dubbo.rpc.support.RpcUtils;

import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;

import static org.apache.dubbo.common.constants.CommonConstants.TIMESTAMP_KEY;
import static org.apache.dubbo.common.constants.RegistryConstants.REGISTRY_SERVICE_REFERENCE_PATH;
import static org.apache.dubbo.rpc.cluster.Constants.WEIGHT_KEY;

/**
 * This class select one provider from multiple providers randomly.
 * You can define weights for each provider:
 * If the weights are all the same then it will use random.nextInt(number of invokers).
 * If the weights are different then it will use random.nextInt(w1 + w2 + ... + wn)
 * Note that if the performance of the machine is better than others, you can set a larger weight.
 * If the performance is not so good, you can set a smaller weight.
 */
public class RandomLoadBalance extends AbstractLoadBalance {

    public static final String NAME = "random";

    /**
     * Select one invoker between a list using a random criteria
     *
     * @param invokers   List of possible invokers
     * @param url        URL
     * @param invocation Invocation
     * @param <T>
     * @return The selected invoker
     *
     *随机权重 负载均衡算法
     */
    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        // Number of invokers
        int length = invokers.size();

        // 判断是否需要权重随机算法
        if (!needWeightLoadBalance(invokers, invocation)) {
            return invokers.get(ThreadLocalRandom.current().nextInt(length));
        }

        // Every invoker has the same weight?
        // 默认 提供者 invoker 都是相同的权重
        boolean sameWeight = true;

        // the maxWeight of every invoker, the minWeight = 0 or the maxWeight of the last invoker
        // 每个提供者 invoker 的权重和值
        int[] weights = new int[length];
        // The sum of weights

        int totalWeight = 0;

        for (int i = 0; i < length; i++) {
            // 获取权重
            int weight = getWeight(invokers.get(i), invocation);
            // Sum
            // 权重相加
            totalWeight += weight;
            // save for later use
            //设置当前索引 i 位 invoker 的权重和值
            weights[i] = totalWeight;

            // 判断每个提供者权重是否不相等
            if (sameWeight && totalWeight != weight * (i + 1)) {

                sameWeight = false;
            }
        }
        // 权重不相同的情况
        if (totalWeight > 0 && !sameWeight) {
            // If (not every invoker has the same weight & at least one invoker's weight>0), select randomly based on totalWeight.
            // 根据权重的总和获取一个随机数
            int offset = ThreadLocalRandom.current().nextInt(totalWeight);
            // Return an invoker based on the random value.
            /**
             * 案例：
             * 如果提供者数量小于等于 4
             *  提供者（权重）:   A（2）      B（3）   C（2）     D（4）  totalWeight = 11
             *  权重和值：       0+2=2      2+3=5    5+2=7     7+4 =11
             *  权重范围：       0-1         2-4      5-6      7-10
             *  权重总和： totalWeight = 11
             *  生成的随机数：offset = 9
             *
             * 1. 随机数9 不小于  A 提供者 的 权重和值 2 。不采用 A
             * 2. 随机数9 不小于  B 提供者 的 权重和值 5 。不采用 B
             * 3. 随机数9 不小于  C 提供者 的 权重和值 7 。不采用 C
             * 4. 随机数9 小于  D 提供者 的 权重和值 10 。采用 D
             *
             */
            if (length <= 4) {
                // 遍历提供者数量
                for (int i = 0; i < length; i++) {
                    // 随机数 小于 该提供者权限和值
                    if (offset < weights[i]) {
                        // 找到并退出
                        return invokers.get(i);
                    }
                }
            } else {
                /**
                 * 案例：
                 * 如果提供者数量等于 10
                 *  提供者（权重）:   A（2）      B（3）   C（2）     D（4）       E（15）     F（12）      G（8）      H（3）    I（6）     J（13）    totalWeight = 68
                 *  权重和值：       0+2=2      2+3=5    5+2=7     7+4 =11    11+15=26   26+12=38    38+8=46    46+3=49   49+6=55   55+13=68
                 *  权重范围：       0-1         2-4      5-6      7-10       11-25      26-37       38-45      46-48     49-54     55-67
                 *  权重总和： totalWeight = 68
                 *  生成的随机数：offset = 21
                 *
                 * 1. 现在有A B C D E F G H I J 10个服务提供者 .也知道它们的权重和值.我们把它们权重和值分为两类: 一类为 负数 ,另一类为正数
                 *       负数为: 未命中 权重和值
                 *       正数为: 命中 权重和值
                 * 2. Arrays.binarySearch(weights, offset) 这个是利用了二分查找.如果是随机数刚好命中权重和值相等 会返回这个 权重和值 数组的索引位置,如:
                 *    命中权重和值 : offset = 38 ,38 可用肉眼看到 对应的提供者是 F,索引值为 5;F 权重范围 是 26-37 不满足权重范围.
                 *                通过 二分查找 Arrays.binarySearch(weights, 38) 会得到 38 的索引位置为 5
                 *                那么就向上查找 索引值 5+1 找了到索引为6的 G 提供者;G 权重范围 是 38-45 满足权重范围.
                 *    为命中权重和值: offset = 44 ,44 可用肉眼看到 对应的提供者是 G,索引值为 6;F 权重范围 是 38-45 是满足权重范围.
                 *                 通过 二分查找 Arrays.binarySearch(weights, 44) 会得到 符合它权重和值 "下一位" 提供者的索引位置.H服务提供者索引为 7.
                 *                 最后 7-1 得到 索引为6 的 G提供者.
                 *
                 *  最后逻辑思路总结: 负向下查找,正向上查找
                 */

                int i = Arrays.binarySearch(weights, offset);

                // 如果小于0
                if (i < 0) {
                    // 向下查找 索引-1; -i取反 如: -9 会变成 正数 9 (哎!java基础都忘得差不多了,不经常使用根本记不住!)
                    i = -i - 1;
                } else {
                    // 向上查找,索引 +1
                    while (weights[i+1] == offset) {
                        i++;
                    }

                    i++;
                }
                // 最终找到并退出
                return invokers.get(i);
            }
        }

        // If all invokers have the same weight value or totalWeight=0, return evenly.
        // 代码执行到这步，证明是全部提供者权重是相同的
        return invokers.get(ThreadLocalRandom.current().nextInt(length));
    }

    private <T> boolean needWeightLoadBalance(List<Invoker<T>> invokers, Invocation invocation) {
        Invoker<T> invoker = invokers.get(0);
        URL invokerUrl = invoker.getUrl();
        if (invoker instanceof ClusterInvoker) {
            invokerUrl = ((ClusterInvoker<?>) invoker).getRegistryUrl();
        }

        // Multiple registry scenario, load balance among multiple registries.
        if (REGISTRY_SERVICE_REFERENCE_PATH.equals(invokerUrl.getServiceInterface())) {
            String weight = invokerUrl.getParameter(WEIGHT_KEY);
            return StringUtils.isNotEmpty(weight);
        } else {
            String weight = invokerUrl.getMethodParameter(RpcUtils.getMethodName(invocation), WEIGHT_KEY);
            if (StringUtils.isNotEmpty(weight)) {
                return true;
            } else {
                String timeStamp = invoker.getUrl().getParameter(TIMESTAMP_KEY);
                return StringUtils.isNotEmpty(timeStamp);
            }
        }
    }
}
